package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * LevelOrderBottom 二叉树的层序遍历[从底往上遍历]
 * Description:
 * Given a binary tree, return the bottom-up level order traversal of its nodes' values.
 * (ie, from left to right, level by level from leaf to root).
 * Input:
 * --3
 * -/ \
 * 9  20
 * --/  \
 * -15   7
 * <p>
 * Output:
 * [
 * [15,7],
 * [9,20],
 * [3]
 * ]
 * Created by heqianqian on 2017/9/13.
 */
public class LevelOrderBottom {

    public static void main(String[] args) {
        /*data preparation*/
        TreeNode root = new TreeNode(3);
        TreeNode rChild = new TreeNode(20);
        rChild.left = new TreeNode(15);
        rChild.right = new TreeNode(7);
        root.left = new TreeNode(9);
        root.right = rChild;

        LevelOrderBottom lob = new LevelOrderBottom();
        List<List<Integer>> lists = lob.levelOrderBottom(root);
        System.out.println(lists);
    }

    /*
     * @param root: A tree
     * @return: buttom-up level order a list of lists of integer
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // write your code here
        List<List<Integer>> lists = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            //每次添加到集合首部
            lists.add(0,list);
        }
        return lists;
    }
}
